/**
 * Copyright 2012
 * VAN
 */
package vaidyaa.algorithms.sorting;

/**
 * @author vaidyaa
 * 
 */
public class QuickSortService implements SortService {

	@Override
	public void sort(Integer[] array, boolean order) {
		int start = 0;
		int end = array.length - 1;
		quickSort(array, start, end, order);
	}

	private void quickSort(Integer array[], int start, int end, boolean order) {
		if (start < end) {
			int middle = (start + end) / 2;
			int partitionIndex = partition(array, start, middle, end, order);
			quickSort(array, start, partitionIndex - 1, order);
			quickSort(array, partitionIndex + 1, end, order);
		}
	}

	private int partition(Integer array[], int start, int pivot, int end,
			boolean order) {
		Integer pivotValue = array[pivot];
		SortingCommons.swap(array, pivot, end);
		int storeIndex = start;
		for (int i = start; i < end; i++) {
			if (!SortingCommons.compare(array[i],pivotValue,order)) {
				SortingCommons.swap(array, i, storeIndex);
				storeIndex++;
			}
		}
		SortingCommons.swap(array, storeIndex, end);
		return storeIndex;
	}
}
